// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
// 所有数字都是正整数。
// 解集不能包含重复的组合
// 思路，回溯

function combinationSum3(k, n) {
    let result = []
    let path = []
    function backtracking(startIndex, sum) {
        if (sum > n) {
            return
        }
        if(path.length === k) {
            if(sum === n) {
                result.push([...path])
            }
            return
        }
        for (let i = startIndex; i <= 9 - (k - path.length) + 1; i++) {
            path.push(i)   
            backtracking(i + 1, sum + i)
            path.pop()         
        }
    }
    backtracking(1, 0)
    return result
}

console.log(combinationSum3(2, 10))